package 剑指Offer1;

public class _19树的子结构 {
    public class TreeNode {
       int val;
       TreeNode left;
       TreeNode right;
       TreeNode(int x) { val = x; }
    }

    /*
        判断以树A是否存在以树B为根节点的子树
        判断树A的左子树中是否存在以B为根节点的子树
        判断树A的右子树是否存在以以B为根节点的子树
     */
    public boolean isSubStructure(TreeNode A, TreeNode B) {
       if(A == null || B == null) return false;
       return helper(A,B) || isSubStructure(A.left,B) || isSubStructure(A.right,B);
    }

    //函数定义：传入两个节点，判断以两个节点为根节点的子树是否相同
    //类似先序遍历
    public boolean helper(TreeNode A,TreeNode B){
        if(B == null) return true;
        if(A == null || A.val!=B.val) return false;
        return helper(A.left,B.left) && helper(A.right,B.right);
    }
}
